#include <stdio.h>

#define MaxSize 50
typedef int ElemType;
typedef struct {
    ElemType data[MaxSize];
    int top;
}SqStack;

//初始化栈
void InitStack(SqStack &S){
    S.top == -1;/*//带头结点的顺序栈*/
}

//判断栈是否为空
bool StackEmpty(SqStack &S){
    if(S.top == -1){
        return true;
    } else{
        return false;
    }
}

//入栈
bool Push(SqStack &S,ElemType x){
    if(S.top == MaxSize - 1){
        return false;
    }
    S.top++;
    S.data[S.top] = x;
    return true;
}

//出栈
bool Pop(SqStack &S,ElemType &x){
    if(S.top == -1){
        return false;
    }
    x = S.data[S.top];
    S.top--;
    return true;
}

//读取栈顶元素
ElemType GetTop(SqStack &S){
    if(S.top == -1){
        return false;
    }
    return S.data[S.top];
}

/*在做题的时候突发奇想——能否写一个函数，使其能够打印出一组元素所有的出栈顺序？*/
//打印所有的出栈顺序（回溯算法）
#define MAX_SIZE 5

// 全局变量用于存储当前的出栈序列
int outSequence[MAX_SIZE];
int outIndex = 0;

// 全局变量用于存储当前的栈
int stack[MAX_SIZE];
int top = -1;

// 计数器，用于给每种情况编号
int count = 0;

// 打印当前的出栈序列
void printSequence() {
    printf("%d: ", ++count);
    for (int i = 0; i < MAX_SIZE; i++) {
        printf("%d ", outSequence[i]);
    }
    printf("\n");
}

// 递归函数，模拟入栈和出栈操作
void stackPermutations(int pushNum, int n) {//生成 pushmum ~ n 的所有出栈顺序
    if (pushNum > n && top == -1) {
        // 所有元素都已处理且栈为空，打印出栈序列
        printSequence();
        return;
    }

    // 选择入栈
    if (pushNum <= n) {
        stack[++top] = pushNum;
        stackPermutations(pushNum + 1, n);
        top--; // 回溯
    }

    // 选择出栈
    if (top >= 0) {
        int temp = stack[top--];
        outSequence[outIndex++] = temp;
        stackPermutations(pushNum, n);
        // 回溯
        stack[++top] = temp;
        outIndex--;
    }
}

int main() {
    printf("所有可能的出栈顺序（共%d种）：\n", 42); // 5个元素的出栈顺序共有C(10,5)/6=42种
    stackPermutations(1, MAX_SIZE); //生成1-5的所有出栈顺序
    return 0;
}

